package demo1;

/**
 * @ClassName H
 * @Description  泛型哈希桶类
 * @Author ZJX
 * @Date 2024/8/10 22:34
 * @Version 1.0
 */
public class HashBucket2<K,V> {

    static class Node<K,V>{

        public K key;
        public V val;

        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }

    }

    public Node<K,V>[] array;
    public int size;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBucket2() {
        array = createArray(16); // 初始容量为16
        size = 0;
    }

    public HashBucket2(int initialCapacity) {
        array = createArray(initialCapacity);
        size = 0;
    }

    // 计算哈希值
    private int hash(K key) {
        int hash = key.hashCode();
        return hash % array.length;
    }

    // 插入或更新键值对
    public void put(K key, V val) {
        int index = hash(key);
        Node<K, V> node = array[index];
        while (node != null) {
            if (node.key.equals(key)) {
                node.val = val;
                return;
            }
            node = node.next;
        }
        Node<K, V> newNode = new Node<>(key, val);
        newNode.next = array[index];
        array[index] = newNode;
        size++;

        // 检查是否需要扩容
        if (size > array.length * DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    // 查找值
    public V get(K key) {
        int index = hash(key);
        Node<K, V> node = array[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.val;
            }
            node = node.next;
        }
        return null; // 未找到
    }

    // 删除键值对
    public V remove(K key) {
        int index = hash(key);
        Node<K, V> node = array[index];
        Node<K, V> prev = null;

        while (node != null) {
            if (node.key.equals(key)) {
                if (prev == null) {
                    array[index] = node.next;
                } else {
                    prev.next = node.next;
                }
                size--;
                return node.val;
            }
            prev = node;
            node = node.next;
        }
        return null; // 未找到
    }

    // 扩容哈希表
    private void resize() {
        Node<K, V>[] newArray = createArray(array.length * 2);

        for (int i = 0; i < array.length; i++) {
            Node<K, V> node = array[i];
            while (node != null) {
                Node<K, V> next = node.next;
                int index = node.key.hashCode() % newArray.length;
                node.next = newArray[index];
                newArray[index] = node;
                node = next;
            }
        }
        array = newArray;
    }

    // 创建数组的方法，避免类型转换的警告
    private Node<K, V>[] createArray(int size) {
        return (Node<K, V>[]) new Node[size];
    }

    // 返回当前哈希桶大小
    public int size() {
        return size;
    }

    // 判断哈希桶是否为空
    public boolean isEmpty() {
        return size == 0;
    }

}
